import java.util.ArrayList;
import java.util.List;

/**
 * @ClassName LCSLength
 * @Description TODO
 * @Author Quentin_zyj
 * @Date 2021/11/2 10:36
 */
public class LCSLength {

    /**
     * 求最长公共子序列
     *
     * @param m 序列x的长度
     * @param n 序列y的长度
     * @param x 序列x
     * @param y 序列y
     * @param c c[i][j]表示Xi和Yj的最长公共子序列的长度
     * @param b b[i][j]记录c[i][j]的值是由哪个子问题的解得到的
     */
    public static void lcsLength(int m, int n, char[] x, char[] y, int[][] c, int[][] b) {
        for (int i = 1; i <= m; i++) {
            c[i][0] = 0;
        }
        for (int i = 1; i <= n; i++) {
            c[0][i] = 0;
        }
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (x[i] == y[j]) {
                    c[i][j] = c[i - 1][j - 1] + 1;
                    b[i][j] = 1;
                } else if (c[i - 1][j] >= c[i][j - 1]) {
                    c[i][j] = c[i - 1][j];
                    b[i][j] = 2;
                } else {
                    c[i][j] = c[i][j - 1];
                    b[i][j] = 3;
                }
            }
        }
    }

    static List<Character> list = new ArrayList<>();

    public static void LCS(int i, int j, char[] x, int[][] b) {
        if (i == 0 || j == 0)
            return;
        if (b[i][j] == 1) {
            LCS(i - 1, j - 1, x, b);
            list.add(x[i]);
        } else if (b[i][j] == 2) {
            LCS(i - 1, j, x, b);
        } else {
            LCS(i, j - 1, x, b);
        }
    }


}
